"""
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

思路，想构建一个平衡的二叉搜索数，就要取列表中间的那个值做根节点

这样下一个节点应该也是剩下的取中间值．

let me try
"""

from leetcode_test import TreeNode
from typing import List


class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def helper(half_list):
            # print(half_list)
            if not half_list:
                return
            mid = len(half_list) // 2
            root = TreeNode(half_list[mid])
            root.left = helper(half_list[:mid])
            root.right = helper(half_list[mid + 1 :])
            return root

        root = helper(nums)
        return root


if __name__ == "__main__":
    # t = TreeNode.create([0,-3,9,-10,None,5])
    t = Solution().sortedArrayToBST([])
    print(t.get_value())
